/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    int max = arr1[0];
    *returnSize = 0;
    for (int i = 0; i < arr1Size; i++) {
        if (max < arr1[i]) {
            max = arr1[i];
        }
    }
    int* hash = (int*)malloc(sizeof(int) * (max + 1));
    if(hash != NULL)
        memset(hash, 0, sizeof(int) * (max + 1));
    for (int i = 0; i < arr1Size; i++) {
        hash[arr1[i]]++;
    }
    int* ans = (int*)malloc(sizeof(int) * arr1Size);
    //写法一
    /*for (int x = 0; x < arr2Size; x++) {
        while(hash[arr2[x]]--){
            ans[(*returnSize)++] = arr2[x];
        }
        hash[arr2[x]] = 0; //while循环时注意hash[arr2[x]]--会多执行一次，须另外将其赋值成0
    }
    for (int x = 0; x <= max; x++) {
        while(hash[x]--) {
            ans[(*returnSize)++] = x;
        }
    }*/ 
    //写法二
    for (int x = 0; x < arr2Size; x++) {
        for (int i = 0; i < hash[arr2[x]]; i++) {
            ans[(*returnSize)++] = arr2[x];
        }
        hash[arr2[x]] = 0;
    }
    for (int x = 0; x <= max; x++) {
        for (int i = 0; i < hash[x]; i++) {
            ans[(*returnSize)++] = x;
        }
    }
    free(hash);
    return ans;
}

/*给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。*/